package fpTree;

import java.util.AbstractSet;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Set;

/**
 * Modified from 
 * 		com.google.common.collect.Set
 */
public class PowerSet<E> implements Iterator<Set<E>>{
	
	//testing
//	public static void main(String args[]) throws IOException {
//		Set<String> alphabet = new LinkedHashSet<String>();
//		for (int i = 0; i < 32; i++) {
//			alphabet.add(i + "");
//		}
//		PowerSet<String> powerSet = new PowerSet<String>(alphabet);
//		Iterator<Set<String>> iterator = powerSet;
//		int i = 0;
//		long j = 1; 
//		while (iterator.hasNext()) {
//			i++;
//			Set<String> set = iterator.next();
//			if ((i %= 10000000) == 0) {
//				System.out.println(set);
//			}
//			if (j++ == (long) 1 << (long) alphabet.size()) {
//				System.out.println("last: " + set);
//				System.out.println(j++ + " : " + ((long) 1 << (long) alphabet.size()));
//			}
//		}
//	}
	
    final Set<E> inputSet;
    final List<E> inputList;
    final long powerSetSize;
    long position;
    
    PowerSet(Set<E> input) {
    	this.inputSet = input;
    	this.inputList = new ArrayList<E>(input);
    	this.powerSetSize = (long) 1 << (long) input.size();
    	this.position = 0;
    }
    
	@Override
	public boolean hasNext() {
		return position < powerSetSize;
	}
	
    @Override 
    public Set<E> next() {
    	if (!hasNext()) {
    		throw new NoSuchElementException();
    	}
    	return get(position++);
    }

    @Override
    public void remove() {
    	throw new UnsupportedOperationException();
    }

    // returns one set from powerset
    public Set<E> get(final long setBits) {
    	return new AbstractSet<E>() {
    		@Override public int size() {
    			return Long.bitCount(setBits);
    		}
    		@Override public Iterator<E> iterator() {
    			return new BitFilteredSetIterator<E>(inputList, setBits);
    		}
    	};
    }
    
    
    private static final class BitFilteredSetIterator<E> implements Iterator<E> {
    	final List<E> input;
    	long remainingSetBits;

    	BitFilteredSetIterator(List<E> input, long setBits) {
    		this.input = input;
    		this.remainingSetBits = setBits;
    	}

    	@Override public boolean hasNext() {
    		return remainingSetBits != 0;
    	}

    	@Override public E next() {
    		int index = Long.numberOfTrailingZeros(remainingSetBits);
    		if (index == 64) {
    			throw new NoSuchElementException();
    		}

    		long currentElementMask = 1 << index;
    		remainingSetBits &= ~currentElementMask;
    		return input.get(index);
    	}

    	@Override
    	public void remove() {
    		throw new UnsupportedOperationException();
    	}
    }
}
